package com.jhy.review.paixu;

import java.util.PriorityQueue;

/**
 * @author go_jhy
 * @create 2022/6/13 - 下午 7:25
 * 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元
 * 素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的
 * 排序算法针对这个数据进行排序
 */
public class Code04_SortArrayDistanceLessK {


    public static void sortedArrDistanceLessK(int[] arr, int k) {
        //默认为小根堆 这是一个优先级队列
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        //首先我们在里面加数据 构建一个k大小的堆
        //这里加一个min的最小值的原因是什么防止恶意的数据
        int index = 0;
        for (; index <= Math.min(arr.length, k); index++) {
            heap.add(arr[index]);
        }
        //现在就是一个0~k范围的的小根堆了
        int i = 0;
        for (; i < arr.length; i++,index++) {
            //继续往这个堆里面加数据,当没有这个数可以加的时候
            heap.add(arr[index]);
            //将最小的值弹出来 赋值为arr[i]
            arr[i] =  heap.poll();
        }
        //当arr[index]当中没有什么数可以加的时候，也就是上面一个循环没有什么东西可以加了。但是最后几个index还有几个数需要弹出。
        while(!heap.isEmpty()){
            arr[i++] = heap.poll();
        }
    }



}
